/**
* Created with CLion.
* User:Lenovo
* Date:2023-04-10
* Time:10:58
* Description:复杂度
*/

#include <stdio.h>

int main()
{
    //衡量算法性能 - 复杂度

    //时间复杂度 - 算法运行时间快慢
    {
        //使用函数 O(...) 表示
        //计算代码的执行次数 - 大 O 的渐进表示法 - 估算
            // 1.用常数 1 取代运行时间中的所有加法常数
            // 2.在修改后的运行次数函数中，只保留最高阶项
            // 3.如果最高阶项存在且不是 1，则去除与这个项目相乘的常数，得到的结果就是大 O 阶

        // O(1) 不是代表一次，是代表常数次

        //最好情况，最坏情况和平均情况
        //最好情况 - 最小运行次数
        //最坏情况 - 最大运行次数
        //平均情况 - 期望运行次数
        //一般情况下关注的是算法的最坏运行情况

        //冒泡排序的时间复杂度是 O(N^2)
        //二分查找的时间复杂度是 O(logN) - 表示以 2 为底数的对数
    }

    //空间复杂度
    {
        //表示算法在运行过程中临时占用空间大小的量度
        //也使用大 O 的渐进表示法
        //主要通过函数在运行时候显式申请的额外空间来确定
        //建立栈帧的空间也算在空间复杂度中

        // fib 函数的空间复杂度是 O(N) - 空间是可以重复利用的，但是时间不能

        //三段逆置实现左旋
        // 1.前 k 个逆置
        // 2.后 n - k 个逆置
        // 3.整体逆置
    }

    return 0;
}